package code.oldCode.classic150;

import java.util.*;

/**
 * @author cuihaoran
 * @date 2024/12/13
 */
public class Classic150_stack {

    /* 20. 有效的括号 */
    public boolean isValid(String s) {
        int len = s.length();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.empty())
                    return false;
                char c1 = stack.peek();
                if (c1 == '(' && c == ')' || c1 == '[' && c == ']' || c1 == '{' && c == '}')
                    stack.pop();
                else
                    return false;
            }
        }
        return stack.empty();
    }

    /* 71. 简化路径 */
    public String simplifyPath(String path) {
        // 去除多余的/
        StringBuilder sb = new StringBuilder();
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < path.length(); i++) {
            if (path.charAt(i) == '/' && (i == 0 || path.charAt(i - 1) == '/' || i == path.length() - 1))
                continue;
            else
                sb.append(path.charAt(i));
        }
        String s = sb.toString();
        // 分割为单独的字符串进行栈处理
        String[] split = s.split("/");
        for (String string : split) {
            if (string.equals("."))
                continue;
            else if (string.equals("..")) {
                if (!stack.empty()) {
                    stack.pop();
                } else
                    continue;
            } else
                stack.push(string);
        }
        // 为空直接返回
        if (stack.empty())
            return "/";
        // 得到答案
        String[] ans = new String[stack.size()];
        while (!stack.empty()) {
            ans[stack.size() - 1] = stack.pop();
        }
        sb = new StringBuilder();
        for (String an : ans) {
            sb.append("/");
            sb.append(an);
        }
        return sb.toString();
    }

    /* 155. 最小栈 */
    class MinStack {

        private Stack<Integer> stack;
        private Stack<Integer> minStack;

        public MinStack() {
            stack = new Stack<>();
            minStack = new Stack<>();
            minStack.push(Integer.MAX_VALUE);
        }

        public void push(int val) {
            stack.push(val);
            minStack.push(Math.min(val, minStack.peek()));
        }

        public void pop() {
            Integer pop = stack.pop();
            minStack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }

    /* 150. 逆波兰表达式求值 */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (token.charAt(0) >= '0' && token.charAt(0) <= '9' || token.length() > 1) {
                stack.push(Integer.parseInt(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
                    case "+" -> stack.push(num1 + num2);
                    case "-" -> stack.push(num1 - num2);
                    case "*" -> stack.push(num1 * num2);
                    case "/" -> stack.push(num1 / num2);
                }
            }
        }
        return stack.peek();
    }

    /* 224. 基本计算器 */
    public int calculate(String s) {
        // 初始化
        Map<Character, Integer> map = new HashMap<>();
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);
        // 去除空格
        s = s.replace(" ", "");
        // -x 变为 0-x
        int len = s.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '-' && (i == 0 || s.charAt(i - 1) == '('))
                sb.append('0');
            sb.append(c);
        }
        char[] charArray = sb.toString().toCharArray();
        len = charArray.length;
        // 遍历
        Deque<Integer> numDeque = new ArrayDeque<>();
        Deque<Character> opDeque = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            char c = charArray[i];
            // 是数字，入操作数栈
            if (Character.isDigit(c)) {
                int num = 0;
                int j = i;
                while (j < len && Character.isDigit(charArray[j])) {
                    num = num * 10 + (charArray[j] - '0');
                    j++;
                }
                i = j - 1;
                numDeque.push(num);
            }
            // 左括号
            else if (c == '(') {
                opDeque.push(c);
            }
            // 右括号
            else if (c == ')') {
                while (!opDeque.isEmpty() && opDeque.peek() != '(') {
                    calculate(numDeque, opDeque);
                }
                opDeque.pop();
            }
            // 是操作
            else {
                while (!opDeque.isEmpty() && opDeque.peek() != '(') {
                    if (map.get(opDeque.peek()) >= map.get(c)) {
                        calculate(numDeque, opDeque);
                    } else {
                        break;
                    }
                }
                opDeque.push(c);
            }
        }
        while (!opDeque.isEmpty()) {
            calculate(numDeque, opDeque);
        }

        return numDeque.peek();
    }

    private void calculate(Deque<Integer> numDeque, Deque<Character> opDeque) {
        int num2 = numDeque.pop();
        int num1 = numDeque.pop();
        switch (opDeque.pop()) {
            case '+' -> {
                numDeque.push(num1 + num2);
            }
            case '-' -> {
                numDeque.push(num1 - num2);
            }
            case '*' -> {
                numDeque.push(num1 * num2);
            }
            case '/' -> {
                numDeque.push(num1 / num2);
            }
        }
    }

    public static void main(String[] args) {
        Classic150_stack classic150Part2 = new Classic150_stack();
        System.out.println(classic150Part2.calculate("0-(1+(4+5+2)-3)+(6+8)"));
    }
}
